package com.lie.prepare.sort;

import org.junit.Test;
import static com.lie.prepare.sort.util.MyArrayHelper.*;

/**
 * Created by lie on 2018/4/18.
 */
public class MergeSort {
    private static void merge(int[] array, int mid, int left, int right){

        int indexLeft = left;
        int indexRight = mid+1;
        int[] temp = new int[right- left+ 1];
        int indexTemp = 0;

        while (indexLeft <= mid && indexRight <= right) {
            if (array[indexLeft]< array[indexRight]){
                temp[indexTemp++] = array[indexLeft++];
            }else {
                temp[indexTemp++] = array[indexRight++];
            }
        }

        while (indexLeft <= mid) {
            temp[indexLeft++] = array[indexLeft++];
        }
        while (indexRight <= right) {
            temp[indexRight++] = array[indexRight++];
        }

        for (int k = 0; k < temp.length; k++) {
            array[left++] = temp[k++];
        }
    }
    private static void devide(int[] array, int left, int right){
        if (left < right) {
            int mid = (left + right) /2;
            devide(array, left, mid);
            devide(array, mid+1, right);
            merge(array, mid, left, right);
        }
    }

    public static void sort(int[] array){
        devide(array, 0, array.length-1);
    }

    @Test
    public void test(){
        int[] array = getArray();
        sort(array);
        printArraySort(array);
    }
}
